import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class test3 {
    public static void main(String[] args) {
        int x = 1024, y = 2024;
        System.out.println(gcd(x,y));
        System.out.println(x*y/gcd(x,y));
    }
    static int gcd(int x, int y){
        return y==0?x:gcd(y,x%y);
    }
    static boolean dfs(int i, int j, char[] t, char[] s){
        if(j == s.length) return true;
        if(i == t.length) return false;
        boolean res = dfs(i+1, j, t, s);
        if(res || t[i] == s[j] && dfs(i+1, j+1, t, s)){
            return true;
        }
        return false;
    }
    static String t = "LFR";//(0,1,2) - 1 = (-1,0,1)
    //西:(0, -1) 北：(-1, 0) 东：(0, 1) 南：(1, 0)
    static int[][] dirct = new int[][]{{0,-1},{-1,0},{0,1},{1,0}};
    static Set<Long> set = new HashSet<>();
    static long dfs(int i, int x, int y, int k, int d, char[] s){
        if(i == s.length){
            return k==0&&set.add(x*100000L+y)?1:0;
        }
        int idx = t.indexOf(s[i]) - 1;
        int new_d = (idx + d + 4)%4;
        long res = dfs(i+1, x+dirct[new_d][0], y+dirct[new_d][1], k, new_d, s);
        if(k > 0){
            char c = s[i];
            for(int j=0; j<2; j++){
                if(c == t.charAt(j)) continue;
                s[i] = t.charAt(j);
                idx = t.indexOf(s[i]) - 1;
                new_d = (idx + d + 4)%4;
                res += dfs(i+1, x+dirct[new_d][0], y+dirct[new_d][1], k-1, new_d, s);;
                s[i] = c;
            }
        }
        return res;
    }
    //49271 - (95)
    static int ans = 0;
    static int[] m = new int[101];
    static void dfs1(int i, int s){
        if(i == 100) return;
        if(s%24 == 0) {
            ans = Math.max(s, ans);
            System.out.println(ans);
        }
        dfs1(i+1, s);
        dfs1(i+1, s+a[i]);
    }
    static int[] a = {534, 386, 319, 692, 169, 338, 521, 713, 640, 692, 969, 362, 311, 349, 308, 357, 515, 140, 591, 216,
            57, 252, 575, 630, 95, 274, 328, 614, 18, 605, 17, 980, 166, 112, 997, 37, 584, 64, 442, 495,
            821, 459, 453, 597, 187, 734, 827, 950, 679, 78, 769, 661, 452, 983, 356, 217, 394, 342, 697, 878,
            475, 250, 468, 33, 966, 742, 436, 343, 255, 944, 588, 734, 540, 508, 779, 881, 153, 928, 764, 703,
            459, 840, 949, 500, 648, 163, 547, 780, 749, 132, 546, 199, 701, 448, 265, 263, 87, 45, 828, 634};
    static int[] memo = new int[2025];
    static int dfs(int i){
        if(i > 2024) return Integer.MAX_VALUE/2;
        if(i == 2024) return 0;
        if(memo[i] != -1) return memo[i];
        int res = dfs(i+1) + 1;
        res = Math.min(res, dfs(i*2)+10);
        int mx = 1, x = i;
        while(x > 0){
            mx = Math.max(mx, x%10);
            x /= 10;
        }
        res = Math.min(res, dfs(i+mx)+3);
        return memo[i] = res;
    }
    static int solve1(){
        int x = 2024;
        int y = 0;
        for(int i=1; i<=x; i++){
            int t = x ^ i;
            if(t < x) y++;
        }
        return y;
    }
    static int solve(){
        int x = 2024;
        int y = 0;
        for(int i=2; i<x; i++){
            if(x%i == 0 && check(i)){
                y = Math.max(y, i);
            }
        }
        return y;
    }
    static boolean check(int x){
        for(int j=2; j<x; j++){
            if(x%j == 0) return false;
        }
        return true;
    }
}

class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        in.nextLine();
        while(t-- > 0){
            char[] s = in.nextLine().toCharArray();
            int n = s.length;
            //boolean flg = dfs(n-1, 0, s);
            //System.out.println(flg?"YES":"NO");
            boolean[][] f = new boolean[n][9];
            int x = s[0] - '0';
            f[0][x%9] = true;
            if(x*x < 10) f[0][x*x%9] = true;
            System.out.println(Arrays.toString(f[0]));
            for(int i=1; i<n; i++){
                x = s[i] - '0';
                for(int j=0; j<9; j++){
                    if(f[i-1][j]) {
                        f[i][(j + x) % 9] = true;
                        if (x * x < 10)
                            f[i][(j + x * x) % 9] = true;
                    }
                }
            }
            System.out.println(f[n-1][0]?"YES":"NO");
        }
    }
}
//60 % 9 = 6%9 = 6
//600 % 9 = 6%9
